package com.链表;

/**
 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 *
 * 示例:
 *
 * 输入:
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 输出: 1->1->2->3->4->4->5->6
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 合并K个排序链表 {
    static class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists.length ==0){
                return null;
            }
            ListNode head = new ListNode(-1);
            ListNode curr = head;

            for(ListNode node:lists){
                while (node != null){
                    curr.next = node;
                    node = node.next;
                    curr = curr.next;
                }
            }
            head = head.next;
           ListNode cur = null,tail = null;
           cur = head;
           while (cur.next != tail){
               while (cur.next != tail){
                   if(cur.val > cur.next.val){
                       int temp = cur.val;
                       cur.val = cur.next.val;
                       cur.next.val = temp;
                   }
                   cur = cur.next;
               }
               tail = cur;
               cur = head;
           }



            return head;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode[] head=  new ListNode[3];
        head[0] = new ListNode(new int[]{9,8,6});
        head[1] = new ListNode(new int[]{1,2,3});
        head[2] = new ListNode(new int[]{4,5,6});
        solution.mergeKLists(head);

    }
}
